In 2001, Farhi et al. proposed a novel quantum computing model, the adiabatic quantum computation (AQC).^[1] The adiabatic quantum computation has proved to be computational equivalent to the quantum circuit model^[2,3] and robustness against thermal fluctuations.^[4–6] Therefore, it has received extensive attention, and several quantum adiabatic algorithms (QAAs) have been proposed and demonstrated, e.g., adiabatic algorithms for unstructured search,^[7] Deutsch–Jozsa problem,^[8–12] Bernstein–Vazirani problem,^[13] Simon’s problem,^[13–15] and integer number factorization problem.^[16–18]

A general QAA is achieved as follows. One first designs the target Hamiltonian H_p, whose ground state encodes the solution of the problem, and then prepare the system in the ground state of the initial Hamiltonian H₀. After adiabatically evolving from H₀ to H_p, which is achieved by means of a linearly interpolating Hamiltonian H (s(t)) = (1 − s)H₀ + sH_p, with s(0) = 0 and s(T ) = 1, the system will finally evolve to the ground state of H_p, and the solution is therefore obtained.

The quantum adiabatic condition^[19] 1 max0≤t≤T|〈E1(t)|∂∂tH(t)|E0(t)〉||Δ(t)|2∼ε≪1

guarantees the adiabaticity during the evolution, where |E₀ (t)〉 and |E₁ (t)〉 are the instantaneous ground state and first excited state of H (t), Δ(t) denotes the energy gap between these two energy levels. The computational complexity of a QAA, regarding to the run time T, can be estimated using the adiabatic condition (1) as well. However, the estimation of Δ(t) in expression (1) is a hard problem. Hence the complexity of some QAAs might be difficult to analyze.

In 2005, Siu introduced the unitary interpolation method^[20] to achieve the time-dependent Hamiltonian H (t), in which the time dependent Hamiltonian has the form 2 H(t)=U(t)H0U†(t),

where U (0) = I, and U (T )H₀U^† (T ) = H_p. Then Sarandy and Lidar proposed an adiabatic implementation of the Deutsch– Jozsa algorithm using unitary interpolation.^[10] It can be proved that the energy gap keep invariant in such method. Therefore, it is much easier to obtain the time complexity using unitary interpolation.

In this paper, we present two alternative QAAs for Bernstein–Vazirani problem and Simon’s problem, where the time-dependent Hamiltonians H (t) are achieved by means of unitary interpolation. We show that the Bernstein–Vazirani problem and Simon’s problem can be solved by using quantum adiabatic algorithms in O(1) and O(n) runtime, respectively, which is the same as the quantum circuit model.

In Bernsterin–Vazirani problem, we are given an n-bit function 3 fa(x)=a⋅x:=a0x0⊕a1x1⊕⋯⊕an−1xn−1.

The task is to determine the n-bit a. Classically, the problem can be solved within n queries of f (·), while the Bernsterin–Vazirani algorithm^[21] in quantum circuit model only requires a single query of f (·) to achieve the same task.

The initial Hamiltonian for solving the Bernstein– Vazirani problem is 4 H0=I−|+〉〈+|,

where we have normalized the energy scale to unity.

The ground state of H₀ is |+〉, which is an equal superposition over all n-bit string 5 |+〉=12n∑x∈{0,1}n|x〉.

The target Hamiltonian is 6 Hp=UH0U†=I−U|+〉〈+|U†,

with the unitary operator 7 U=∑x∈{0,1}neiπ(a⋅x)|x〉〈x|,

and the ground state of H_p is 8 U|+〉=12n∑x∈{0,1}n(−1)(a⋅x)|x〉.

The QAA for Bernsterin–Vazirani problem is achieved as follows.

Step 1 Prepare |+〉, which is the ground state of H₀, as the initial state of the quantum system 9 |ψ(t=0)〉=|+〉.

Step 2 Adiabatically evolve the system from H₀ to the target Hamiltonian H_P, under the following time-dependent Hamiltonian 10 H(t)=U(t)H0U†(t),

where the unitary operator 11 U(t)=∑x∈{0,1}neiπ(a⋅x)tT|x〉〈x|.

The unitary operator can be realized by U (t) = exp(−iH_at) with Hamiltonian Ha=−πT∑x∈{0,1}n(a⋅x)|x〉〈x|.

Under the adiabatic approximation, the system finally evolves to the ground state of H_p, which is |ψ(t=T)〉≈U|+〉=12n∑x∈{0,1}neiπ(a⋅x)|x〉.

The final state can be rewritten in x-basis. Define and , then 12 |0〉=12(|0′〉+|1′〉),|1〉=12(|0′〉−|1′〉).

The above equations can be summarized in more concise form as 13 |x〉=12∑y=0,1(−1)xy|y′〉.

For the n-bit case, the state |x〉 is 14 |x〉=12n∑y∈{0,1}n(−1)x⋅y|y′〉.

Then the final state can be rewritten as 15 |ψ(t=T)〉≈U|+〉=12n∑x∈{0,1}n∑y∈{0,1}n(−1)x⋅y+x⋅a|y′〉.

Notice that 12n∑x∈{0,1}n∑y∈{0,1}n(−1)x⋅y+x⋅a=δay,

then |ψ (t = T)〉 ≈ U |+〉 = |a′〉.

Step 3 At the end of the evolution, measure each qubit of the system in the {|0′〉,|1′〉} basis, and a can be obtained.

The run time of the algorithm is determined by the adiabatic condition 16 max0≤t≤T|〈E1(t)|∂∂tH(t)|E0(t)〉||Δ(t)|2∼ε≪1.

Obviously, the energy gap is invariant during the adiabatic evolution, i.e., Δ(t) = Δ(0) = 1. On the other hand, 17 |〈E1(t)|∂∂tH(t)|E0(t)〉|=|〈E1(t)|(∂∂tU(t))H0U†(t)|E0(t)〉+〈E1(t)|U(t)H0(∂∂tU†(t))|E0(t)〉|.

As , and H_a is commutative with U (t) and U^† (t), therefore 18 |〈E1(t)|∂∂tH(t)|E0(t)〉|=|〈E1|[H0,Ha]|E0〉|=Δ(0)|〈E1|Ha|E0〉|.

Note that any eigenvalue λ of H_a satisfies |λ| ≤ π/T, therefore |〈E₁|H_a |E₀〉| ≤ π/T . Thus 19 max0≤t≤T|〈E1(t)|∂∂tH(t)|E0(t)〉||Δ(t)|2≤πT∼ε,

and the total evolution time 20 T∼πε,

that means the algorithm can be achieved in O(1) run time, which is the same order as the algorithm using quantum circuit mode.

In Simon’s problem, a function from n-bit strings to n-bit strings is given by 21 f:{0,1}n→{0,1}n,x→f(x),

where we are given the promise that there is one unknown string a = a₁a₂ ⋯a_n so that f (x) = f (y) (x ≠ y) if and only if y = x ⊕ a.

In order to find a, namely the period of the function, classical algorithm requires exponentially queries of f (·), while Simon’s algorithm in quantum circuit model requires only O(n) queries.^[22]

Here, we propose a QAA for Simon’s problem. We choose the initial Hamiltonian 22 H0=I2n−|+〉〈+|⊗|0〉〈0|.

The algorithm requires two n-bit registers with the first one encodes the inputs and the second one records the output of f (·).

Meanwhile, the target Hamiltonian is designed as Hp=UH0U†=I2n−U|+〉〈+|⊗|0〉〈0|U†,

The unitary operator is U=∑x∈{0,1}n|x〉〈x|⊗e[−i(π/2)f1(x)σx,1]e[−i(π/2)f2(x)σx,2]⋯e[−i(π/2)fn(x)σx,n],

where σ_x,i is the σ_x operator acting on the i-th bit of the second register, and f_i (x) denotes the i-th bit of f(x).

The ground state of H_p is 23 U|+〉|0〉=12nU∑x∈{0,1}n|x〉|0〉=12n∑x∈{0,1}n|x〉⊗|f1(x)〉|f2(x)〉⋯|fn(x)〉=12n∑x∈{0,1}n|x〉⊗|f(x)〉.

The quantum adiabatic algorithm for Simon’s problem proceeds as the following steps.

Step 1 Prepare the ground state of H₀, as the initial state of the quantum system. |ψ(t=0)〉=|+〉|0〉.

Step 2 Adiabatically evolve the system from H₀ to the target Hamiltonian H_p, by means of the time-dependent Hamiltonian H(t)=U(t)H0U†(t),

where the unitary operator U(t)=∑x∈{0,1}n|x〉〈x|⊗exp⁡[−iπ2tT∑i=1nfi(x)σx,i].

The unitary operator can be realized by U (t) = exp(−iH_at) with Hamiltonian Ha=π2T∑x∈{0,1}n(|x〉〈x|⊗∑i=1nfi(x)σx,i).

At the end of the evolution, we approximately obtain the ground state of H_p |ψ(t=T)〉≈U|+〉=12n∑x∈{0,1}n|x〉⊗|f(x)〉.

Step 3 Measure the second register, and obtain some values |f (y)〉, then the first register will be collapsed to the state , which can be rewritten in the {|0′〉,|1′〉} basis as 12(|y〉+|y⊕a〉)=12n(∑z∈{0,1}n(−1)y⋅z|z′〉+∑z∈{0,1}n(−1)(y⊕a)⋅z|z′〉)=12n−1∑a:z=0(−1)y⋅z|z′〉.

Step 4 Measure the first register in the {|0′〉,|1′〉} basis, some values z which satisfy a · z = 0 can be obtained randomly.

Repeating from Step 1 to Step 4 m times, it yields the following linear equation 24 {a⋅z1=0,a⋅z2=0,⋯a⋅zm=0.

It can be proved that for m = n + O(1), a can be uniquely determined from Eq. (24) with probability at least 2/3,^[23], so the QAA for Simon problem requires O(n) evaluations of f .

Same as in Section 2, energy gap Δ(t) = Δ(0). From the adiabatic condition, max0≤t≤T|〈E1(t)|∂∂tH(t)|E0(t)〉||Δ(t)|2=max0≤t≤T|〈E1|Ha|E0||Δ(t)|≤π2T≤ε,

the run time of each cycle is T ≥ π/2ɛ. Therefore, the complexity of the algorithm is O(n).

We first compare our scheme with Ref. [13]. In Ref. [13], I. Hen has proposed the QAAs for the same two problems as well, but his algorithms are significantly different from ours. On the one hand, in our work, the algorithms are devised using unitary interpolation, while in Ref. [13] the algorithms are achieved in linear interpolation. On the other hand, in Ref. [13], the ground states of the Hamiltonian is highly degenerate, and higher levels of coherence are needed,^[13] in addition, the adiabatic evolution is achieved in each invariant subspaces, which is different from the traditional AQC model. While, in our work the ground state is unique, which indicates that the two alternative algorithms we proposed can be more robust against noises.

We now discuss the physical realization. The initial and target Hamiltonians in our schemes are one-dimensional projectors, i.e., H = I − |α〉〈α|. It is n-local Hamiltonian, which cannot be physically realized. In the QAA for Bernstein–Vazirani problem, we can take alternative 1-local initial Hamiltonian H0=−σx,1−σx,1−⋯−σx,n

with energy gap Δ(0) = 1, and the time-dependent Hamiltonian is H(t)=U(t)H0U†(t)=−∑k[σx,kcos⁡(πTakt)+σy,ksin⁡(πTakt)].

which keeps 1-local during the evolution. From the adiabatic condition (1), the algorithm can also be achieved in O(1) running time.

However, in the QAA for Simon’s problem, the two registers are correlated after adiabatic evolution, and might be entangled. It means that the target Hamiltonian might be n-local and not physically realizable, even the initial Hamiltonian is chosen to be 1-local. Nevertheless, like other oracle-based adiabatic algorithms with n-local Hamiltonians, our algorithm provides a meaningful example to investigate some aspects of QAC, such as the role of coherence,^[24] and performances in open system.^[10,25]

In summary, we have proposed two quantum adiabatic algorithms for Bernstein–Vazirani problem and Simon’s problem. The algorithm for Bernstein–Vazirani problem has an O(1) complexity, and the complexity of the algorithm for Simon’s problem is O(n). Both of the two algorithms have the same complexities as the algorithms in quantum circuit model. In further studies, we would like to find more realizable algorithms using local Hamiltonian, and extend the unitary interpolation method to devise other quantum adiabatic algorithms, such as unstructured search problem and prime factorization problem.